package leetcode_zh

/**
 * @Description: 118. 杨辉三角 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/27 21:18
 **/
func generate(numRows int) [][]int {
	if numRows == 1 {
		return [][]int{{1}}
	}
	var res = [][]int{{1}, {1, 1}}
	if numRows == 2 {
		return res
	}
	for i := 3; i <= numRows; i++ {
		var cur = []int{1}
		for j := 1; j < i-1; j++ {
			cur = append(cur, res[i-2][j-1]+res[i-2][j])
		}
		cur = append(cur, 1)
		res = append(res, cur)
	}
	return res
}

/**
 * @Description: 1137. 第 N 个泰波那契数 简单
 * @Keyword: 好简单
 * @Author: kami
 * @Date: 2022/5/28 7:41
 **/
func tribonacci(n int) int {
	if n == 0 {
		return 0
	} else if n <= 2 {
		return 1
	}
	var dp = []int{0, 1, 1}
	for i := 3; i <= n; i++ {
		dp = append(dp, dp[i-1]+dp[i-2]+dp[i-3])
	}
	return dp[n]
}

/**
 * @Description: 1646. 获取生成数组中的最大值 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/28 7:47
 **/
func getMaximumGenerated(n int) int {
	if n == 0 {
		return 0
	}
	var dp = make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	var max = dp[1]
	for i := 2; i <= n; i++ {
		var half = i / 2
		// 偶数
		if i%2 == 0 {
			dp[i] = dp[half]
		} else {
			dp[i] = dp[half] + dp[half+1]
		}
		if dp[i] > max {
			max = dp[i]
		}
	}
	return max
}

/**
 * @Description: 1186. 删除一次得到子数组最大和 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/28 18:09
 **/
func maximumSum(arr []int) int {
	var dp = make([][2]int, len(arr))
	dp[0][0] = arr[0] // 没有删除
	dp[0][1] = arr[0] // 删除1个
	var res = arr[0]
	for i := 1; i < len(arr); i++ {
		dp[i][0] = getMax(dp[i-1][0]+arr[i], arr[i])
		dp[i][1] = getMax(dp[i-1][1]+arr[i], dp[i-1][0])
		res = getMax(dp[i][0], dp[i][1], res)
	}
	return res
}

/**
 * @Description: 1191. K 次串联后最大子数组之和 中等
 * @Keyword: 当 k = 1 时，答案为当前数组的最大子序和（参考股票问题）
			当 k >= 2 时，令sum 为原数组的和；
			k1 为 k = 1 时的答案；
			k2 为 最大前缀和 + sum - 最小前缀和（类似示例2的情况）；
			注意到，
			若 sum >= 0，则 k2 >= k1, 因此答案为 k2 + (k - 2) * sum;
			若 sum < 0，则不能保证 k2 >= k1，但是 (k-2) * sum < 0，故不能添加，因此答案为 max(k1, k2)。
			故答案可统一为 max(k1, k2) + max((k - 2)*sum，0)。
 * @Author: kami
 * @Date: 2022/5/28 19:28
 **/
func kConcatenationMaxSum(arr []int, k int) int {
	var N = len(arr)
	var preMinSum = 0 // 最小前缀和
	var preMaxSum = 0 // 最大前缀和
	var subMaxSum = 0 // 最大子数组和
	var sum = 0       // 数组和
	for i := 0; i < N; i++ {
		sum += arr[i]
		if sum < preMinSum {
			preMinSum = sum
		}
		if sum > preMaxSum {
			preMaxSum = sum
		}
		if sum-preMinSum > subMaxSum {
			subMaxSum = sum - preMinSum
		}
	}

	var k2 = preMaxSum + sum - preMinSum
	if k == 1 {
		return subMaxSum % 1000000007
	}
	return (getMax(subMaxSum, k2) + getMax((k-2)*sum, 0)) % 1000000007
}

/**
 * @Description: 62. 不同路径 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/30 13:27
 **/
func uniquePaths(m int, n int) int {
	var dp = make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

/**
 * @Description: 63. 不同路径 II 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/30 14:45
 **/
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	var dp = make([][]int, m)
	var meetObstacle bool
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
		if meetObstacle {
			dp[i][0] = 0
		} else {
			if obstacleGrid[i][0] == 1 {
				meetObstacle = true
				dp[i][0] = 0
			} else {
				dp[i][0] = 1
			}

		}
	}
	meetObstacle = false
	for i := 0; i < n; i++ {
		if meetObstacle {
			dp[0][i] = 0
		} else {
			if obstacleGrid[0][i] == 1 {
				meetObstacle = true
				dp[0][i] = 0
			} else {
				dp[0][i] = 1
			}
		}
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if obstacleGrid[i][j] == 1 {
				continue
			}
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

/**
 * @Description: 64. 最小路径和 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/5/30 15:00
 **/
func minPathSum(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	var dp = make([][]int, m)
	dp[0] = make([]int, n)
	dp[0][0] = grid[0][0]
	for i := 1; i < m; i++ {
		dp[i] = make([]int, n)
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for i := 1; i < n; i++ {
		dp[0][i] = dp[0][i-1] + grid[0][i]
	}

	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = grid[i][j] + getMin(dp[i-1][j], dp[i][j-1])
		}
	}
	return dp[m-1][n-1]
}
